package baseclass.j_dp.dp.oneZeroBag;


import java.util.Arrays;

/**
 * 给定一个正数数组和一个正数aim。
 * 判断aim是否可由数组arr中任意数的组合(重复index不可以重复用)。
 *
 * @date 2020/3/2 16:53
 */
public class Code02_SumTargetInArr {
    public static boolean process1(int[] arr, int index, int sum, int aim) {
        if (sum >= aim) return sum == aim;
        if (index >= arr.length) return false;
        //当前位置要或不要
        return
                process1(arr, index + 1, sum, aim) ||
                        process1(arr, index + 1, sum + arr[index], aim);
    }

    /**
     * TODO  此方法描述的有问题
     * 带记忆性回溯,memo[i][j]代表遍历到i后，当前和为j时，能否满足条件
     */
    public static boolean process2(int[] arr, int aim) {
        if (arr == null || arr.length == 0) return false;
        int sum = 0;
        for (int i : arr) sum += i;
        if (sum < aim) return false;
        //0代表未知，-1代表不可以，1代表可以
        int[][] memo = new int[arr.length][aim + 1];
        return dpProcess2(arr, 0, 0, aim, memo);
    }


    private static boolean dpProcess2(int[] arr, int index, int sum, int aim, int[][] memo) {
        if (sum >= aim) return sum == aim;
        if (index >= arr.length) return sum == aim;
        if (memo[index][sum] != 0) return memo[index][sum] == 1;

        boolean res = dpProcess2(arr, index + 1, sum, aim, memo) ||
                dpProcess2(arr, index + 1, sum + arr[index], aim, memo);
        memo[index][sum] = res ? 1 : -1;
        return res;
    }

    /**
     * 方式3：看成背包。 aim看做背包的质量.
     * dp[i][j]表示决策完第i元素后，和为j下能否满足条件
     */
    public static boolean process3(int[] arr, int aim) {
        if (arr == null || arr.length == 0) return false;
        int sum = 0;
        for (int i : arr) sum += i;
        if (sum < aim) return false;
        boolean[][] dp = new boolean[arr.length][aim + 1];
        //决策0号元素时，只有sum = 0 或 sum = num[0]才是true
        for (int j = 0; j <= aim; j++) {
            dp[0][j] = (j == 0 || j == arr[0]);
        }
        //从1号元素决策
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                //第i号元素不要
                dp[i][j] = dp[i - 1][j];
                //i号元素要
                if (j - arr[i] >= 0)
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i]];
            }
        }
        return dp[arr.length - 1][aim];
    }

    /**
     * 空间优化
     */
    public static boolean process4(int[] arr, int aim) {
        if (arr == null || arr.length == 0) return false;
        int sum = 0;
        for (int i : arr) sum += i;
        if (sum < aim) return false;
        boolean[] dp = new boolean[aim + 1];
        for (int j = 0; j <= aim; j++) {
            dp[j] = (j == 0 || j == arr[0]);
        }
        for (int i = 1; i < arr.length; i++) {
            /*for (int j = aim; j >=0 ; j--) {
                //dp[j] = dp[j];
                if(j - arr[i] >= 0){
                    dp[j] = dp[j] || dp[j-arr[i]];
                }
            }*/
            //上面代码等价于
            for (int j = aim; j >= arr[i]; j--) {
                dp[j] = dp[j] || dp[j - arr[i]];
            }
        }
        return dp[aim];
    }

    public static void main(String[] args) {
        System.out.println(process3(new int[]{7, 3, 3, 15, 16, 16}, 14));
        System.out.println(process4(new int[]{7, 3, 3, 15, 16, 16}, 14));
        System.out.println(process2(new int[]{7, 3, 3, 15, 16, 16}, 10));
        System.out.println(process1(new int[]{7, 3, 3, 15, 16, 16}, 0, 0, 14));
        for (int i = 0; i < 10000; i++) {
            int[] arr = generateRandomArray(10, 20);
            int aim = (int) (Math.random() * 21);
            try {
                if (process2(arr, aim) != process4(arr, aim)) {
                    System.out.println("出错的数组:" + Arrays.toString(arr));
                    System.out.println("aim = " + aim);
                    break;
                }
            } catch (Exception e) {
                System.out.println(Arrays.toString(arr));
                break;
            }

        }
    }

    // for test
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        //产生 [0-maxsize]随机长度的数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            //随机产生数据
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }
}
